import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by forcht on 2018/7/14.
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            int target3=target-num[i];
            for(int j=i+1;j<num.length;j++){
                int target2=target3-num[j];
                int left=j+1;
                int right=num.length-1;
                while (left<right){
                    if(left<right&&num[left]+num[right]<target2)left++;
                    else if(left<right&&num[left]+num[right]>target2)right--;
                    else if (left<right&&num[left]+num[right]==target2){
                        ArrayList<Integer> integers=new ArrayList<>();
                        integers.add(num[i]);
                        integers.add(num[j]);
                        integers.add(num[left]);
                        integers.add(num[right]);
                        list.add(integers);
                        left++;
                        right--;
                        while (left<right&&num[left]==integers.get(2))left++;
                        while (left<right&&num[right]==integers.get(3))right--;
                    }
                }
                while (j+1<num.length&&num[j]==num[j+1])j++;
            }
            while (i+1<num.length&&num[i]==num[i+1])i++;
        }
        return list;
    }
}
